iT邦幫忙

2023 iThome 鐵人賽
DAY 21
1
Software Development

那些前端不用會，但是可以會的資料結構與演算法系列 第 21 篇

【排序演算法】快速排序法 Quick Sort

15th鐵人賽 快速排序法 quick sort
1778 瀏覽

  • 分享至 

  • xImage
    •  

本文同步更新於個人網站中，有更好的排版和程式碼區塊 highlighting 支援。

快速排序法（Quick Sort）是對氣泡排序法的一種改進，是一個基於分治法（Divide and Conquer）的排序演算法。它不像 merge sort 那樣一上來就將陣列切成“碎片”，而是逐漸對要處理的陣列進行切割，每次切成兩部分，讓其左邊都小於某個數，右邊都大於某個數，然後再對左右兩邊進行同樣的操作（快速排序），直到每個子陣列長度為 1，原陣列就會變成有序的了。

從下面這段程式碼來具體理解一下，它的基本架構如下：

function quickSort (array) {
  function QuickSort(array, left, right) {
    if (left < right) {
      let index = partition(array, left, right);
      QuickSort(array, left, index - 1);
      QuickSort(array, index + 1, right);
    }
  }

  QuickSort(array, 0, array.length - 1);
  return array;
}

function partition(array, left, right) { // D&C function
  // TODO
}

quickSort 是一個進入點，它會呼叫遞迴函式 QuickSort。QuickSort 內部有一個 partition 輔助函式，它會選中某個元素作為基準值（pivot，分界值），實作對子陣列的左右切割，保證左邊的元素都比 pivot 小，右邊的元素都比 pivot 大，最後回傳 pivot 的索引值，方便再對左右兩陣列呼叫 QuickSort。

Quick Sort 的常用方法

對於 quick sort 的 partition 函式的實作，通常有以下 3 種。

1. 左右指標法

使用左右指標法實作 partition 方法的步驟如下：

  1. 選取某個元素作為 pivot，一般取目前陣列的第一個或最後一個元素，這裡採用最後一個元素。
  2. 從 left 一直向後尋找，直到找到一個大於 pivot 的值，而 right 則從後往前尋找，直到找到一個小於 pivot 的值，然後交換兩元素的位置。
  3. 重複步驟 2，直到 left 與 right 相遇，此時將 pivot 放置在 left 的位置即可。

當 left >= right 時，一趟 quick sort 就完成了，這時將 pivot 和 array[left] 的值進行一次交換：

function partition(array, left, right) {
  const pivot = array[right];
  let pivotIndex = right;

  while (left < right) {
    while (left < right && array[left] <= pivot) {
      // 1. 防止越界需要 left < right
      // 2. array[left] <= pivot 因為可能存在相同元素
      left++; // 找到比 pivot 大的數
    }
    while (left < right && array[right] >= pivot) {
      right--; // 找到比 pivot 小的數
    }
    swap(array, left, right);
  }
  // 最後一個比 pivot 大的 left 元素要與 pivot 交換
  swap(array, left, pivotIndex);
  return left; // 回傳的是中間的位置
}

上面程式碼的執行過程可以參考這張圖：

https://ithelp.ithome.com.tw/upload/images/20231006/20152758BQpOX35rWF.png

2. 挖坑法

使用挖坑法實作 partition 方法的步驟如下：

  1. 選取某個元素作為 pivot，這裡選擇第 1 個元素，將“它”挖出來（這只是概念上的挖，它兩側的數不會趁機佔領這個位置）。於是這個位置就是最初的“坑”。
  2. 從 left 一直向後尋找，直到找到一個大於 pivot 的值，然後將該元素填入坑中，坑位變成了 array[left]。
  3. 從 right 一直向前尋找，直到找到一個小於 pivot 的值，然後將該元素填入坑中，坑位變成了 array[right]。
  4. 重複步驟 2、3，直到 left 與 right 相遇，然後將 pivot 填入最後一個坑位。

挖坑法的程式碼實作如下：

function partition(array, left, right) {
  const pivot = array[right]; // 坑位為 array[right]
  while (left < right) {
    while (left < right && array[left] <= pivot) {
      left++;
    }
    array[right] = array[left]; // 坑位變成 array[left]
    while (left < right && array[right] >= pivot) {
      right--;
    }
    array[left] = array[right]; // 坑位變成 array[right]
  }
  array[right] = pivot;
  return left;
}

坑位在程式碼上的變化如下：

array[left] -> array[right] -> array[left] -> array[right] -> ...

這是填坑的示意圖：

https://ithelp.ithome.com.tw/upload/images/20231006/20152758gVY25KIkdS.png

挖坑法比左右指標法好理解，並且不依賴額外的 swap 函式，具體執行過程可以參考下面這張圖：

https://ithelp.ithome.com.tw/upload/images/20231006/20152758kWJLcceC0t.jpg

3. 前後指標法

使用前後指標法實作 partition 方法的步驟如下：

定義兩個指標，一前一後，前面的指標尋找比 pivot 小的元素，後面的指標尋找比 pivot 大的元素。前面的指標找到符合條件的元素後，將前後指標所指向的元素交換位置，當前面的指標遍歷完整個陣列時，將 pivot 與後指標的後一位交換位置，然後回傳後指標的位置。

function partition(array, left, right) {
  const pivot = array[right];
  let curr = left; // 找比 pivot 大的數
  let prev = curr - 1; // 找比 pivot 小的數

  while (curr <= right) {
    if (array[curr] <= pivot && ++prev !== curr) {
      swap(array, prev, curr);
    }
    curr++;
  }
  return prev;
}

前後指標法的執行過程可以參考下面這張圖：

https://ithelp.ithome.com.tw/upload/images/20231006/20152758Q9mT0Cn5u1.png

這個方法最大的優勢是支援對鏈結串列（Linked List）進行排序，而左右指標法和挖坑法只能針對陣列進行排序。

Optimization

Quick Sort 的最佳化主要涉及到三個方面：

  1. pivot 的選擇。最好和最壞情況的區別就是選取 pivot 不正確導致的。之前的程式碼裡，我們會選擇第一個或是最後一個元素作為 pivot，但太大或太小的元素都會影響效率。於是我們有了三數取中位數法，即隨機取 3 個元素進行排序，然後取中間的元素作為 pivot，一般我們會取第一個、中間的、最後一個元素。如果排序的陣列非常大，還可以進行九數取中位，取三次樣本，每次取三個元素，然後再取這三個元素的中位數，最後再取這三個中位數的中位數作為 pivot。
  2. 改進不必要的交換。我們將 pivot 備份到 A[0] 中，像在前文中使用 swap 方法時一樣，我們只需要做交換的工作，最終 A[i] 與 A[j] 融合，再將 A[0] 位置的數值賦值回 A[i]。因為沒有了多次交換的操作，所以效率會有所提升。
  3. 改進小陣列時的排序方案。對於很小的和部分有序的陣列，quick sort 的效率不如 insertion sort。因此，我們可以對陣列進行切割，當陣列的大小小於一定的值時，使用 insertion sort 進行排序。（這是以前 Chrome V8 引擎的 sort 實作方式）

待排序序列長度 N = 10，在 5 和 20 之間任一截止範圍都有可能產生類似效果。下面是小陣列使用 insertion sort 的程式碼：

if (high - low + 1 < 10) {
  insertionSort(array, low, high);
  return;
} else {
  quickSort(array, low, high);
}

完整程式碼如下：

function getMid(array, left, right) {
  const mid = left + Math.floor((right - left) / 2);
  if (array[left] <= array[right]) {
    if (array[mid] < array[left]) {
      return left;
    } else if (array[mid] > array[right]) {
      return right;
    } else {
      return mid;
    }
  } else {
    if (array[mid] < array[right]) {
      return right;
    } else if (array[mid] > array[left]) {
      return left;
    } else {
      return mid;
    }
  }
}

// 左右指標法
function partition(array, left, right) {
  const mid = getMid(array, left, right);
  swap(array, mid, right); // 把 pivot 移到最右邊
  const pivot = array[right];
  let pivotIndex = right;
  while (left < right) {
    while (left < right && array[left] <= pivot) {
      left++;
    }
    while (left < right && array[right] >= pivot) {
      right--;
    }
    swap(array, left, right);
  }
  swap(array, left, pivotIndex);
  return left;
}

// 挖坑法（前後指標法同理）
function partition(array, left, right) {
  const mid = getMid(array, left, right);
  swap(array, mid, right); // 把 pivot 移到最右邊
  const pivot = array[right];
  while (left < right) {
    while (left < right && array[left] <= pivot) {
      left++;
    }
    array[right] = array[left];
    while (left < right && array[right] >= pivot) {
      right--;
    }
    array[left] = array[right];
  }
  array[right] = pivot;
  return left;
}

非遞迴實作方式

遞迴主要是在劃分子區間，如果要用非遞迴的方式實作 quick sort，可以使用一個 stack 來存放區間即可。

要將遞迴程式改造成非遞迴程式，首先想到的就是使用 stack，因為遞迴的本質就是一個 push 元素到 stack 的過程。下面是一個使用 stack 的非遞迴實作方式：

function quickSortStack(array, start, end) {
  const stack = [];
  stack.push(end);
  stack.push(start);
  while (stack.length) {
    const left = stack.pop();
    const right = stack.pop();
    const index = partition(array, left, right);
    if (left < index - 1) {
      stack.push(index - 1);
      stack.push(left);
    }
    if (right > index + 1) {
      stack.push(right);
      stack.push(index + 1);
    }
  }
}

應用 - TopK 問題

給你一個由整數組成的陣列，請找出其中最小的 K 個數。例如，給你的陣列是 [11, 9, 6, 17, 0, 1, 2, 18, 3, 4, 8, 5] 和 K = 4，那麼最小的 4 個數是 [0, 1, 2, 3]。

思路：TopK 問題也可以利用在實作 quick sort 時用到的 quick select 演算法來解決，我們知道 partition 函式會回傳一個 pivot，pivot 左邊的元素都比 pivot 小，右邊的元素都比 pivot 大。我們可以一直去呼叫 partition 函式，直到 pivot 的位置剛好是 K - 1，那麼 pivot 左邊的元素就是最小的 K 個數。

我們打開 day21-quick-sort/getTopK.js 來實作看看：

function getTopK(array, k) {
  if (array.length >= k) {
    let low = 0;
    let high = array.length - 1;
    let pivot = partition(array, low, high);
    // 不斷調整分治的範圍，直到 pivot 的 index 等於 k - 1
    while (pivot !== k - 1) {
      // 大了，往左(前)邊調整
      if (pivot > k - 1) {
        high = pivot - 1;
        pivot = partition(array, low, high);
      }
      // 小了，往右(後)邊調整
      if (pivot < k - 1) {
        low = pivot + 1;
        pivot = partition(array, low, high);
      }
    }

    return array.slice(0, k);
  }
}

複雜度 Complexity

Name Average Best Worst Space Method Stable
Quick sort https://chart.googleapis.com/chart?cht=tx&amp;chl=O(n%20%5Clog%20n) https://chart.googleapis.com/chart?cht=tx&amp;chl=O(n%20%5Clog%20n) https://chart.googleapis.com/chart?cht=tx&amp;chl=O(n%5E2) https://chart.googleapis.com/chart?cht=tx&amp;chl=O(%5Clog%20n) In-place No

參考資料


上一篇
【排序演算法】合併排序法 Merge Sort
下一篇
【排序演算法】計數排序法與桶排序法
系列文
那些前端不用會，但是可以會的資料結構與演算法 共 31 篇
  1. 27
    【回溯法】Backtracking (2)
  2. 28
    【動態規劃】Dynamic Programming (1)
  3. 29
    【動態規劃】Dynamic Programming (2)
  4. 30
    【貪婪演算法】Greedy Algorithm
  5. 31
    完賽雜談
完整目錄
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
902 組
團體組數
37 組
累計文章數
19750 篇
完賽人數
529 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 17th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# linux windows server css react
熱門問題
熱門回答
熱門文章
IT邦幫忙